Conventional shared-memory packet switch architecture makes best use of memory capacity while achieving the optimal delay-throughput properties. However, for N ports, the shared-memory's bandwidth has to be N times each individual port's bandwidth B. For a multiport gigabit packet switch, this requires using expensive fast SRAM and wide memory interfaces for a multiport gigabit packet switch.
Researchers have been working on building fast switches out of memory modules operating at port speeds. For example, an input-queuing switch architecture uses N memory modules of bandwidth B, one for each port. But the basic input-queuing architecture suffers from head-of-line blocking and only achieves about 63% throughput. Although sophisticated scheduling algorithms have been proposed to improve the performance of the input-queuing switches, they have yet to achieve the ideal delay-throughput properties and efficient memory capacity utilization of shared-memory architecture.
Another approach is a shared-multiple-memory module (SMMM) architecture independently proposed by (1) H. Kondoh, H. Notani, and H. Yamanaka of Mitsubishi Electric Corp. in A Shared Multibuffer Architecture for High-Speed ATM Switch LSIs, IEICE Trans. Electron. Vol.E76-C, No.7, July 1993, pp.1094-1101, and S. Wei and V. Kumar of AT&T Bell Labs in (2) On the Multiple Shared Memory Module Approach to ATM Switching, Proceedings of IEEE ICC 1992, pp. 116-23 and (3) Decentralized Control of a Multiple Shared Memory Module ATM Switch, Proceedings of IEEE ICC 1992, pp.704-708, 1992, each of which articles is hereby incorporated by reference.
For SMMM the N input ports are connected to M memory modules which are in turn connected to the N output ports, conceptually through two switch fabrics. Although Bell Labs' switch architecture using either a centralized scheduling scheme in (2) or a decentralized scheduling scheme in (3) can provide an ideal delay-throughput, it requires 2N-1 memory modules, each having a bandwidth B. The Mitsubishi Electric switch requires N memory modules of bandwidth 2B to achieve a reasonable throughput. And while memory architecture has been extensively studied in the context of the multiple processing, because packet switching has a different ordering, that earlier architecture cannot be used for a switch design.
Although for many years memory cell capacity has been increasing exponentially, memory bandwidth has only been increasing linearly. So one object of our invention is to build an N-port switch that only requires N memory modules of bandwidth B, as an input-queuing switch does. This would make it possible to build the fastest switch with a given memory technology or build switches with inexpensive RAMs. Other objects of our invention are to achieve optimal delay-throughput to meet performance requirements and to allow maximum sharing of memory space to enable the switch product to be competitively priced.